Definition

The Kolmogorov complexity of a string xx is

K(x):=CU(x)=min⁡{|⟨M,w⟩|:TM M halts on input w and outputs x}K(x) := C_U(x) = \min\{\lvert \langle M,w \rangle \rvert : \text{TM }M\text{ halts on input }w\text{ and outputs }x\}

(see: halting problem, Turing machine)

See also

References

  1. https://en.wikipedia.org/wiki/Kolmogorov_complexity
  2. https://www.sciencedirect.com/topics/computer-science/kolmogorov-complexity
  3. https://nautil.us/kolmogorov-complexity-and-our-search-for-meaning-237158/
  4. A. C. Šen, Kolmogorov complexity and algorithmic randomness. Providence, Rhode Island: American Mathematical Society, 2017. https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf
  5. https://scottaaronson.blog/?p=791
  6. https://www.cs.cmu.edu/~venkatg/teaching/15252-sp20/notes/Kolmogorov-Complexity.pdf
  7. https://www.lesswrong.com/w/kolmogorov-complexity
  8. https://www.xuzhe.tj.cn/index.php/2024/02/22/柯尔莫戈洛夫复杂性（kolmogorov-complexity）理论/
  9. https://zhuanlan.zhihu.com/p/138258602